COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00008 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a19.tex[106,phy] \today\hfill}

\bigskip
\ctrline{{\bf Got Change for a Dollar?} [RWF:  Recurrences]}

\bigskip
Let $Q(x)$ be the number of ways to change $x$ cents into quarters
(25~cent pieces). $Q(1)=Q(2)=0$; $Q(25)=Q(50)=1$, etc.
Let $QD(x)$ be the number of ways to change $x$~cents into quarters
and dimes. $QD(1)=QD(2)=0$; $QD(10)=QD(25)=QD(30)=1$;
$QD(50)=2$, $QD(100)=3$.
Similarly, $QDN(x)$ is the number of ways to change $x$~cents into
quarters, dimes, and nickels, and $QDNP(x)$ the same using quarters,
dimes, nickels, and pennies. For example, $QDNP(15)=6$, because
15~cents can be:
$$\vcenter{\halign{\hfil#&$\hfil \;#\;\hfil$&\hfil #\hfil%
&$\hfil \;#\;\hfil$&\hfil #\hfil%
&$\hfil \;#\;\hfil$&\hfil #\hfil%
&$\hfil \;#\;\hfil$&\hfil #\hfil%
&$\hfil \;#\;\hfil$&\hfil #\hfil%
&$\hfil \;#\;\hfil$&\hfil #\hfil%
&$\hfil \;#\;\hfil$&\hfil #\hfil%
&$\hfil \;#\;\hfil$&\hfil #\hfil%
&$\hfil \;#\;\hfil$&\hfil #\hfil%
&$\hfil \;#\;\hfil$&\hfil #\hfil%
&$\hfil \;#\;\hfil$&\hfil #\hfil%
&$\hfil \;#\;\hfil$&\hfil #\hfil%
&$\hfil \;#\;\hfil$&\hfil #\hfil%
&$\hfil \;#\;\hfil$&\hfil #\hfil\cr
10&+&5\cr
10&+&1&+&1&+&1&+&1&+&1\cr
5&+&5&+&5\cr
5&+&5&+&1&+&1&+&1&+&1&+&1\cr
5&+&1&+&1&+&1&+&1&+&1&+&1&+&1&+&1&+&1&+&1\cr
1&+&1&+&1&+&1&+&1&+&1&+&1&+&1&+&1&+&1&+&1&+&1&+&1&+&1&+&1\cr}}$$
I want to know how many ways there are to change a dollar using those
four coins; i.e., what is $QDNP(100)$?

Let's compute all four functions, for each value of $x$ from 0 to~100.
Obviously $Q(x)=1$ if $x$ is a positive multiple of~25, and is otherwise~0.
What about $QD(x)$? We can break down the ways of changing $x$ into two
classes:

\medskip
\item{(1)}  Using only quarters, there are $Q(x)$ ways.
\item{(2)}  Using at least one dime, there are $QD(x-10)$ ways to make
up the remaining $x-10$ cents in quarters and dimes.

\medskip\noindent
For example 
$$\eqalign{QD(50)&=Q(50)+QD(40)=1+1=2;\cr
QD(100)&=Q(100)+QD(90)=1+2=3;\cr
QD(110)&=Q(110)+QD(100)=1+3=3\,.\cr}$$
This rule works when $x=10$ if we say that $QD(0)=1$. It works when $x=5$,
if we say $QD(-5)=0$.

After some similar machinations, we arrive at these definitions:
$$\vcenter{\halign{$#\hfil$\qquad&$\hfil #\hfil$\qquad&$\hfil #\hfil$\qquad%
&$\hfil #\hfil$\cr
&x<0&x=0&x>0\cr
\noalign{\smallskip}
Q(x)&0&1&Q(x-25)\cr
QD(x)&0&1&Q(x)+QD(x-10)\cr
QDN(x)&0&1&QD(x)+QDN(x-5)\cr
QDNP(x)&0&1&QDN(x)+QDNP(x-1)\cr}}$$
and this program:

\vfill\eject

\halign{\qquad\tt\lft{#}\cr
FOR I:=-25 TO -1 DO\cr
\qq BEGIN\cr
\qq Q[I]:=0; QD[I]:=0; QDN[I]:=0; QDNP[I]:=0;\cr
\qq END;\cr
Q[0]:=1; QD[0]:=1; QDN[0]:=1; QDNP[1]:=1;\cr
FOR I:=1 TO 100 DO\cr
\qq BEGIN\cr
\qq Q[I]:=Q[I-25];\cr
\qq QD[I]:=Q[I]+QD[I-10];\cr
\qq QDN[I]:=QD[I]+QDN[I-5];\cr
\qq QDNP[I]:=QDN[I]+QDNP[I-1];\cr
\qq END;\cr
WRITELN('A DOLLAR CAN BE CHANGED',QDNP[100],'WAYS')\cr}

The theme of this program, which accounts for its simplicity, is that
the functions are easy to compute for argument~$x$ if you already have
them at hand for all smaller arguments. This is the paradigm of
{\sl dynamic programming\/}, about which more will be said.

\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft September 10, 1984

\bye